Date: Tue, 14 Jan 1997 22:48:45 GMT
Server: NCSA/1.4.1
Content-type: text/html
Last-modified: Thu, 23 May 1996 21:18:07 GMT
Content-length: 16200

<TITLE>Computer System Design--More Information</TITLE>

<center>
<H2>Computer System Design--Additional Information</H2>
G22.2233
<BR>
Thursday 5:00-7:00
<br>
Room 101, CIMS
<BR>
<h4><strong>Pradeep K. Dubey</strong></h4>
<BR>
</center><P>

<!WA0><IMG SRC="http://cs.nyu.edu/cs/dept_info/course_home_pages/spr96/G22.2233/images/line.gif">
<br>
<br>
Back to the <!WA1><A HREF="http://cs.nyu.edu/cs/dept_info/course_home_pages/spr96/G22.2233/index.html">Computer System Design Home Page</A>.<P>

<!WA2><IMG SRC="http://cs.nyu.edu/cs/dept_info/course_home_pages/spr96/G22.2233/images/line.gif">

<H2>Table of Contents</H2>

<p>
<center><table border=1 cellspacing=0 cellpadding=0 width=375>
<tr>
<! Row 1 --------------------->
<td align=center >
<!WA3><A HREF="http://cs.nyu.edu/cs/dept_info/course_home_pages/spr96/G22.2233/more-course-info.html#course-descr">Course Description</A>
</td>
</tr>

<! Row 2 --------------------->
<tr>
<td align=center >
<!WA4><A HREF="http://cs.nyu.edu/cs/dept_info/course_home_pages/spr96/G22.2233/more-course-info.html#instr-descr">About the Instructor</A>
</td>
</tr>

<! Row 3 --------------------->
<tr>
<td align=center >
<!WA5><A HREF="http://cs.nyu.edu/cs/dept_info/course_home_pages/spr96/G22.2233/more-course-info.html#textbook">Textbook</A>
</td>
</tr>

<! Row 4 --------------------->
<tr>
<td align=center >
<!WA6><A HREF="http://cs.nyu.edu/cs/dept_info/course_home_pages/spr96/G22.2233/more-course-info.html#TAinfo">TA Information and How/Where to get Help?</A>
</td>
</tr>

<! Row 5 --------------------->
<tr>
<td align=center >
<!WA7><A HREF="http://cs.nyu.edu/cs/dept_info/course_home_pages/spr96/G22.2233/more-course-info.html#class-news">Class News</A>
</td>
</tr>

<! Row 6 --------------------->
<tr>
<td align=center >
<!WA8><A HREF="http://cs.nyu.edu/cs/dept_info/course_home_pages/spr96/G22.2233/more-course-info.html#class-notes">Class Notes</A>
</td>
</tr>

<! Row 7 --------------------->
<tr>
<td align=center >
<!WA9><A HREF="http://cs.nyu.edu/cs/dept_info/course_home_pages/spr96/G22.2233/more-course-info.html#homework">Homework/Exam Policy</A>
</td>
</tr>

<! Row 8 --------------------->
<tr>
<td align=center >
<!WA10><A HREF="http://cs.nyu.edu/cs/dept_info/course_home_pages/spr96/G22.2233/more-course-info.html#hw-assign">Assigned Homeworks</A>
</td>
</tr>

<! Row 9 --------------------->
<tr>
<td align=center >
<!WA11><A HREF="http://cs.nyu.edu/cs/dept_info/course_home_pages/spr96/G22.2233/more-course-info.html#sol-assign">
Solutions to Assigned Homeworks</A>
</td>
</tr>

</table>
</center>
<br>
<br>
<!WA12><IMG SRC="http://cs.nyu.edu/cs/dept_info/course_home_pages/spr96/G22.2233/images/line.gif">
<H3><A NAME="course-descr">Course Description</A></H3

Prerequisite or corequisite:  G22.1170  (Fundamental Algorithms)
<br>

Intended to give students whose main interest is in software, an
introduction to the important principles of computer organization
and design.  Topics covered include:  logic design basics,
basics of performance evaluation, instruction sets, arithmetic
for computers, processor datapath and control, pipelining,
memmory hierarchy, interfacing processors and peripherals,
parallel processor basics.

<!WA13><IMG SRC="http://cs.nyu.edu/cs/dept_info/course_home_pages/spr96/G22.2233/images/line.gif">
<H3><A NAME="instr-descr">About the Instructor</A></H3>

Pradeep K. Dubey is an Adjunct Assistant Professor at the
Department of Computer Science at New York University.
He is currently employed by
<!WA14><a href="http://www.ibm.com/">IBM</a>
at the
<!WA15><a href="http://www.watson.ibm.com/">T. J. Watson Research Center</a>
as a member of the Advanced RISC Systems group.
He worked for Intel Corporation
<!WA16><a href="http://www.intel.com/">Intel Corporation</a>
from 1984 to 1991 and was on the design teams of the 80386,
80486, and Pentium processors.
He received the B.S. degree in Electronics, with distinction from
<!WA17><a href="http://www.mgmt.purdue.edu/MIS/BIT/bit.html">Birla Institute
of Technology</a>, Mesra, India, in 1982,
M.S. degree in Electrical and Computer engineering from
<!WA18><a href="http://www.umass.edu/">University of Massachusetts</a>
at Amherst, in 1984, and the Ph.D.
in Electrical Engineering from
<!WA19><a href="http://www.purdue.edu/">Purdue University</a> in 1991.
He has also participated in 
<!WA20><a href="http://umunhum.stanford.edu/">advanced processor research</a>
efforts at
<!WA21><a href="http://www.stanford.edu/">Stanford University</a>.
His research interests include
<!WA22><a href="http://www.cs.wisc.edu/~arch/www/">computer architecture</a>
and performance modeling.
He is also a Senior Member of
<!WA23><a href="http://www.ieee.org/">IEEE</a>.

<!WA24><IMG SRC="http://cs.nyu.edu/cs/dept_info/course_home_pages/spr96/G22.2233/images/line.gif">
<H3><A NAME="textbook">Textbook</A></H3>

Patterson and Hennessy, Computer Organization and Design: 
The Hardware / Software Interface, Morgan Kaufmann.

<!WA25><IMG SRC="http://cs.nyu.edu/cs/dept_info/course_home_pages/spr96/G22.2233/images/line.gif">
<H3><A NAME="TAinfo">TA Information</A></H3>

<br>
Fangzhe Chang
<br>
(212)998-3363
<br>
<!WA26><A HREF="mailto:fangzhe@cs.nyu.edu">fangzhe@cs.nyu.edu </A>
<br>
<br>
If you need help with the class material, you have the following four
options:
<ul>
<li>
Send me an email with your question
<li>
Send the TA an email with your question
<li>
Meet me during my office hour right after the class in my office
<li>
Send an email to the TA to set-up a meeting time.
</ul>
<br>
<br>

<!WA27><IMG SRC="http://cs.nyu.edu/cs/dept_info/course_home_pages/spr96/G22.2233/images/line.gif">
<H3><A NAME="class-news">Class News</A></H3>
<blink><strong>Important Announcement:</strong></blink>
<br>
<br>
</TABLE></CENTER><CENTER><H2>Final Exam Score Distribution</H2><TABLE BORDER=3 CELLPADDING=2 WIDTH="50%">
<TR><TH>Range</TH><TH>Number of Students</TH></TR>
<TR><TH ALIGN=center>90-100</TH><TD ALIGN=center>2</TD>
<TR><TH ALIGN=center>81-90</TH><TD ALIGN=center>0</TD>
<TR><TH ALIGN=center>71-80</TH><TD ALIGN=center>2</TD>
<TR><TH ALIGN=center>61-70</TH><TD ALIGN=center>2</TD>
<TR><TH ALIGN=center>51-60</TH><TD ALIGN=center>4</TD>
<TR><TH ALIGN=center>41-50</TH><TD ALIGN=center>4</TD>
<TR><TH ALIGN=center>31-40</TH><TD ALIGN=center>1</TD>
<TR><TH ALIGN=center>21-30</TH><TD ALIGN=center>2</TD>
<TR><TH ALIGN=center>0-20</TH><TD ALIGN=center>0</TD>
</TABLE></CENTER>

<br>
<br>
</TABLE></CENTER><CENTER><H2>Final Grade Distribution</H2><TABLE BORDER=3 CELLPADDING=2 WIDTH="50%">
<TR><TH>Grade</TH><TH>Number of Students</TH></TR>
<TR><TH ALIGN=center>A</TH><TD ALIGN=center>2</TD>
<TR><TH ALIGN=center>B+</TH><TD ALIGN=center>5</TD>
<TR><TH ALIGN=center>B</TH><TD ALIGN=center>3</TD>
<TR><TH ALIGN=center>B-</TH><TD ALIGN=center>4</TD>
<TR><TH ALIGN=center>C+</TH><TD ALIGN=center>2</TD>
<TR><TH ALIGN=center>C</TH><TD ALIGN=center>1</TD>
<TR><TH ALIGN=center>C-</TH><TD ALIGN=center>0</TD>
</TABLE></CENTER>

<br>
<br>
<strong>Final Exam Solutions:</strong>
<!WA28><A HREF="http://cs.nyu.edu/cs/dept_info/course_home_pages/spr96/G22.2233/solutions/solu.ps#solu">Final Exam Solution</A>
<br>
<br>

<strong>Important Announcement:</strong>
Final Exam will be on May 9, 1996 (Thu) from 5-7p in the same class room.
It will cover all the material covered in class lectures and
homeworks upto the last lecture on May 2.
It will be a closed book exam.
<hr>
<strong>Important Announcement:</strong>
Final homework solutions will be posted 
on the course homepage on May 2 (last day of class).  So if you intend
to turn in this homework and have not yet done so,
you must turn it in latest by May 1.
<hr>
In order to not lose a lecture and cover more material,
I have decided not to offer any midterm.  Midterm weight
will be added to the final exam. 
Homework weight stays the same.

<br>
<br>
<strong>SPIM Access Information </strong>
<br>
1. login sparky or slinky or any other machine which can access slinky.b file system.
<br>
2. cd ~fangzhe/spim/bin
<br>
3. type "xspim" or "spim". (xspim provides x-window interface.)
<br>
4. load any .s file in the directory ../Tests
<br>
5. if you like you can add
      /slinky.b/csphd/fangzhe/spim/bin
    in your PATH environment variable
<br>
6. There is documentation available in the directory ~fangzhe/spim/Documentation. You can also read appendix A of the textbook.


<!WA29><IMG SRC="http://cs.nyu.edu/cs/dept_info/course_home_pages/spr96/G22.2233/images/line.gif">
<H3><A NAME="class-notes">Class Notes (postscript files)</A></H3>

<p>
<center><table border=1 cellspacing=0 cellpadding=0 width=375>
<tr>
<! Row 1 --------------------->
<td align=center >
<!WA30><A HREF="http://cs.nyu.edu/cs/dept_info/course_home_pages/spr96/G22.2233/class-notes/class1.ps#class-1">Class-1: 1/25/96</A>
</td>
</tr>

<! Row 2 --------------------->
<tr>
<td align=center >
<!WA31><A HREF="http://cs.nyu.edu/cs/dept_info/course_home_pages/spr96/G22.2233/class-notes/class2.ps#class-2">Class-2: 2/1/96</A>
</td>
</tr>

<! Row 3 --------------------->
<tr>
<td align=center >
<!WA32><A HREF="http://cs.nyu.edu/cs/dept_info/course_home_pages/spr96/G22.2233/class-notes/class3.ps#class-3">Class-3: 2/8/96</A>
</td>
</tr>

<! Row 4 --------------------->
<tr>
<td align=center >
<!WA33><A HREF="http://cs.nyu.edu/cs/dept_info/course_home_pages/spr96/G22.2233/class-notes/class4.ps#class-4">Class-4: 2/15/96</A>
</td>
</tr>

<! Row 5 --------------------->
<tr>
<td align=center >
<!WA34><A HREF="http://cs.nyu.edu/cs/dept_info/course_home_pages/spr96/G22.2233/class-notes/class5.ps#class-5">Class-5: 2/22/96</A>
</td>
</tr>

<! Row 6 --------------------->
<tr>
<td align=center >
<!WA35><A HREF="http://cs.nyu.edu/cs/dept_info/course_home_pages/spr96/G22.2233/class-notes/class6.ps#class-6">Class-6: 2/29/96</A>
</td>
</tr>

<! Row 7 --------------------->
<tr>
<td align=center >
<!WA36><A HREF="http://cs.nyu.edu/cs/dept_info/course_home_pages/spr96/G22.2233/class-notes/class7.ps#class-7">Class-7: 3/7/96</A>
</td>
</tr>

<! Row 8 --------------------->
<tr>
<td align=center >
<!WA37><A HREF="http://cs.nyu.edu/cs/dept_info/course_home_pages/spr96/G22.2233/class-notes/class8.ps#class-8">Class-8: 3/21/96</A>
</td>
</tr>

<! Row 9 --------------------->
<tr>
<td align=center >
<!A HREF="class-notes/class9.ps#class-9">Class-9: 3/28/96 -- Text Chapter 5, Sections 5.1 to 5.3</A>
</td>
</tr>

<! Row 10 --------------------->
<tr>
<td align=center >
<!A HREF="class-notes/class10.ps#class-10">Class-10: 4/4/96 -- Text Chapter 5, Sections 5.4 to 5.5</A>
</td>
</tr>

<! Row 11 --------------------->
<tr>
<td align=center >
<!A HREF="class-notes/class11.ps#class-11">Class-11: 4/11/96 -- Text Chapter 6, Sections 6.1 to 6.6</A>
</td>
</tr>

<! Row 12 --------------------->
<tr>
<td align=center >
Class-12: 4/18/96 -- Chapter 6 completed + <!WA38><A HREF="http://cs.nyu.edu/cs/dept_info/course_home_pages/spr96/G22.2233/class-notes/class12.ps#class-12">Some Additional Material</A>
</td>
</tr>

<! Row 13 --------------------->
<tr>
<td align=center >
Class-12: Chapter 7 + <!WA39><A HREF="http://cs.nyu.edu/cs/dept_info/course_home_pages/spr96/G22.2233/class-notes/class13.ps#class-13">Some Additional Material</A>
</td>
</tr>

<! Row 14 --------------------->
<tr>
<td align=center >
<!A HREF="class-notes/class14.ps#class-14">Class-14: 5/2/96</A>
</td>
</tr>

</table>
</center>
<!WA40><IMG SRC="http://cs.nyu.edu/cs/dept_info/course_home_pages/spr96/G22.2233/images/line.gif">
<H3><A NAME="homework">Homework/Exam Policy</A></H3>

Weightage for final grade:
<br>
<br>
Homeworks: 30 percent
<br>
No Mid-term
<br>
Final: 70 percent
<br>
<br>
Note-1:
<br>
All homeworks regardless of their total points will carry EQUAL
weight in the final grade.
<br>
<br>
Note-2:
<br>
Please note that a good on-time homework record can boost
your final grade, if you are on the fence.
<br>
<br>
Note-3:
<br>
Homeworks may be emailed to the TA (fangzhe@cs.nyu.edu).
For those of you who submit hardcopy homework (instead of email'ing
a soft copy):
<br>
If you plan to return the homework outside the class
and office hours, please make arrangements with the TA
(fangzhe@cs) and leave it in his mailbox instead of mine.
<br>
<br>

<!WA41><IMG SRC="http://cs.nyu.edu/cs/dept_info/course_home_pages/spr96/G22.2233/images/line.gif">
<H3><A NAME="hw-assign">Assigned Homeworks</A></H3>

<hr>
Homework-5:     <blink>Due: Apr 25</blink> (points same as in Text)
<ul>
<li>
5.1 - 5.16 (You can use Fig. 5.47 in Prob. 5.7)
<li>
6.1-6.3, 6.8-6.9
<br>
I strongly urge you to go through the example on pp. 389,
covering Figs. 6.25 to 6.29.
</ul>
<hr>
Homework-4:     <blink>Due: Apr 4</blink> (points same as in Text or shown in large brackets)
<ul>
<li>
4.1 - 4.19
<li>
4.26 - 4.30
<li>
4.39, 4.41, 4.42
<li>
Using the algorithm in Fig. 4.41, carry out the following addition in binary:
-0.625 + 1.4375. Assume 5 bits of precision (4 bits after decimal). You
must show all steps. [10]
<li>
Using the algorithm in Fig. 4.43, carry out the following multiplication in 
binary: -0.625 x 1.4375. Assume 5 bits of precision (4 bits after decimal). You
must show all steps. [10]
</ul>

<hr>
Homework-3:     <blink>Due: Mar 21</blink> (points shown in large brackets)

<ol>
<li>
Text B.7 [15]
<br><br>

<li>
Text B.8 [15]
<br><br>

<li>
Text B.12 [15]
<br><br>

<li>
Consider the following gate called
IMPLICATION gate which implements the following
function: C = A -> B :

<br>
A=F, B=F => C=T
<br>
A=F, B=T => C=T
<br>
A=T, B=F => C=F
<br>
A=T, B=T => C=T
<br>

a) Can you build an invertor using this gate? [5]
<br>
b) Is this gate universal? Explain your answer. [10]
<br><br>


<li>
[I added this problem beyond the ones mentioned in class on 3/7]
<br>
Using the laws of Boolean algebra on page B-6 (without using
truth tables), prove the following:
<ol>
<li>
These are known as "Consensus Theorems": [10]
<ol>
<li>
XY + X'Z + YZ = XY + X'Z
<li>
(X + Y) (X' + Z) (Y + Z) = (X + Y) (X'+ Z)
</ol>
Note-1:  X' refers to complement or invert of X, and so on.
<br>
Note-2: The redundant term "YZ" or "(Y + Z)" are also called 'consensus'
<br>
<blink>Note-3:</blink> Earlier (prior to Mar 18) part 2 had a typo.
The correct third term is (Y+Z).  It was mistyped as: (Y'+Z).
However, Note-2 had the proper redundant term.

<li>
Use the consensus theorems to prove the following: [15]
<br>
ABCD + B'CDE + A'B' + BCE' = A'B' + BCE' + ACDE

<li>
Use the consensus theorem to prove the following addition theorem: [10]
<br>
(X + Y) (X' + Z) = XZ + X'Y

<li>
Use the theorems above to show: [20]
<br>
(A + B + C') (A + D' + E) (A + B + D) (A' + C)
= AC + A'BD' + A'BE + A'C'DE
</ol>
<br><br>

<li>
Show the PLA implementation (similar to Figs. B.6 or B.7) of the following
functions: [10]
<ol>
<li>
F1 = A'BD + ABD + AB'C' + B'C
<li>
F2 = C + A'BD
<li>
F3 = BC + AB'C' + ABD
</ol>
<br><br>

<li>
Text B.13 [15].
<br><br>

<li>
Using D flip-flops and other combinational logic elemnts, if needed,
construct the following:
<ol>
<li>
A 4-bit counter which has the following counting sequence: [10]
0001, 0010, 0100, 1000, 0001, ...

<li>
A 4-bit register which has the initial content of 0000 and shifts left
a '1' on each clock tick, starting at the least-significant-bit
position. [10]

<li>
A 4-bit register which has the initial content of 0000 and shifts right
a '1' on each clock tick, starting at the most-significant-bit
position. [10]
<br>
<blink>Note:</blink> Prior to Mar 18, there was typo here and it incorrectly said:
'least-significant' instead of 'most-significant'.  You cannot
shift right starting as least-significant-bit position!
</ol>
<br><br>


<li>
Modify the state diagram in Fig. B.28 for the following modifed
traffic controler: [15]
<br>
North-South road has priority over East-West road. So, NSlite
should normally be green and trun to red only if a) there
is a car waiting on E-W road and there is no car on N-S road,
or, b) there is a car waiting on E-W road for more than 4 mins.
The EWlite should turn to red if there is no car on E-W road.
or if there is car waiting on N-S road for more than 2 mins.

</ol>

<hr>
<strong>Homework-2:</strong> 	<blink>Due: Mar 7</blink>
(points same as the problem rating given in Text)
<br>
<br>
All problems from the Text, Chapter 3:
<br>
<br>
3.1 through 3.8
<br>
3.12 through 3.22
<br>
3.26
<br>
3.37 through 3.38
<br>
<br>
<hr>
<strong>Homework-1:</strong> 	<blink>Due: Feb 22</blink> (points shown in large brackets)

<br>
<br>
Problem 1:
<br>
Exercise 1.A on slide-11 of class-1 notes [5]
<br>
<br>

Problem 2:
<br>
Repeat Problem 1 with the two cost-model improvements
suggested in slide-11 of class-1 notes. [5]
<br>
<br>

Problem 3:
<br>
Text 2.14 [10], 2.15 [5], 2.16 [10], 2.17 [5], 2.18 [5], 2.19 [10]
<br>
<br>

Problem 4:
<br>
Repeat the class example (slide 26) with System-3
execution times for normalization, i.e., using System-3
execution times as the relative measures of workloads.
In other words, you need to calculate average execution rates
(normalized with respect to System-3 execution times)
of the four systems using unweighted and weighted
versions of arithmetic, geometric, and harmonic means.
Note that the  workload represented by program i,
i.e., w<sub>i</sub> will be given by its execution
time on System-3, i.e., t<sub>i3</sub>.
<br>
[20]
<br>
<br>

Problem 5:
<br>
Text 2.32 [5] 2.33 [10], 2.34 [10]
<br>
<hr>

<!WA42><IMG SRC="http://cs.nyu.edu/cs/dept_info/course_home_pages/spr96/G22.2233/images/line.gif">
<H3><A NAME="hw-sols">Solutions to Assigned Homeworks</A></H3>

<p>
<center><table border=1 cellspacing=0 cellpadding=0 width=375>
<tr>
<! Row 1 --------------------->
<td align=center >
<!WA43><A HREF="http://cs.nyu.edu/cs/dept_info/course_home_pages/spr96/G22.2233/solutions/solutions1.ps#solutions-1">Solutions-1</A>
</td>
</tr>

<tr>
<! Row 2 --------------------->
<td align=center >
<!WA44><A HREF="http://cs.nyu.edu/cs/dept_info/course_home_pages/spr96/G22.2233/solutions/solutions2.ps#solutions-2">Solutions-2</A>
</td>
</tr>

<tr>
<! Row 3 --------------------->
<td align=center >
<!WA45><A HREF="http://cs.nyu.edu/cs/dept_info/course_home_pages/spr96/G22.2233/solutions/sol31.ps#solutions-31">Solutions-3, Part-1</A>
<!WA46><A HREF="http://cs.nyu.edu/cs/dept_info/course_home_pages/spr96/G22.2233/solutions/sol32.ps#solutions-32">Solutions-3, Part-2</A>
<!WA47><A HREF="http://cs.nyu.edu/cs/dept_info/course_home_pages/spr96/G22.2233/solutions/sol33.ps#solutions-33">Solutions-3, Part-3</A>
<!WA48><A HREF="http://cs.nyu.edu/cs/dept_info/course_home_pages/spr96/G22.2233/solutions/sol34.ps#solutions-34">Solutions-3, Part-4</A>
<!WA49><A HREF="http://cs.nyu.edu/cs/dept_info/course_home_pages/spr96/G22.2233/solutions/sol35.ps#solutions-35">Solutions-3, Part-5</A>
<!WA50><A HREF="http://cs.nyu.edu/cs/dept_info/course_home_pages/spr96/G22.2233/solutions/sol36.ps#solutions-36">Solutions-3, Part-6</A>
</td>
</tr>

<tr>
<! Row 4 --------------------->
<td align=center >
<!WA51><A HREF="http://cs.nyu.edu/cs/dept_info/course_home_pages/spr96/G22.2233/solutions/solutions4.ps#solutions-4">Solutions-4</A>
</td>
</tr>

<tr>
<! Row 5 --------------------->
<td align=center >
<!WA52><A HREF="http://cs.nyu.edu/cs/dept_info/course_home_pages/spr96/G22.2233/solutions/solutions5.ps#solutions-1">Solutions-5</A>
</td>
</tr>

</table>
</center>


